// 二叉树先序序列化和反序列化
// 测试链接 : https://leetcode.cn/problems/serialize-and-deserialize-binary-tree/


    // 二叉树可以通过先序、后序或者按层遍历的方式序列化和反序列化
    // 但是，二叉树无法通过中序遍历的方式实现序列化和反序列化
    // 因为不同的两棵树，可能得到同样的中序序列，即便补了空位置也可能一样。
    // 比如如下两棵树
    //         __2
    //        /
    //       1
    //       和
    //       1__
    //          \
    //           2
    // 补足空位置的中序遍历结果都是{ null, 1, null, 2, null}
	// 提交这个类
class Codec {
public
     Encodes a tree to a single string.
    string serialize(TreeNode root) {
        if (!root) return ;
        string result;
        queueTreeNode sq; 
        sq.push(root);
        while (!sq.empty()) {
            TreeNode cur = sq.front();
            sq.pop();
            if (cur != nullptr) {
                result += to_string(cur-val) + ,;
                sq.push(cur-left);
                sq.push(cur-right);
            } else {
                result += #,;
            }
        }

        return result;
    }

     Decodes your encoded data to tree.
    TreeNode deserialize(string data) {
        if (data.empty()) return nullptr;

        vectorstring vals;
        stringstream ss(data);
        string str;
        
        while (getline(ss, str, ',')) {
            vals.push_back(str);
        }
        
        int cnt = 0;
        TreeNode root = generate(vals[cnt++]);
        if (!root) return nullptr;
        
        queueTreeNode q;
        q.push(root);
        while (!q.empty()) {
            TreeNode cur = q.front();
            q.pop();
            
            cur-left = generate(vals[cnt++]);
            cur-right = generate(vals[cnt++]);
            
            if (cur-left != nullptr) {
                q.push(cur-left);
            }
            if (cur-right != nullptr) {
                q.push(cur-right);
            }
        }

        return root;
    }

private
    TreeNode generate(const string& str) {
        return str == #  nullptr  new TreeNode(stoi(str));
    }
};